/**
 * @param {number[]} parent
 * @param {string} s
 * @return {number}
 */
 var longestPath = function(parent, s) {
  const g = {}
  let root = 0
  for(let i = 0; i<parent.length; i++) {
    let p = parent[i]
    if(p === -1) {
      root = i
      continue
    }
    g[p] = g[p] || []
    g[p].push(i)
  }
  const memo = {}
  let ans = 1
  help(root)
  return ans
  function help(root) {
    if(!g[root]) {
      return
    }
    if(memo[root]) {
      ans = Math.max(ans, memo[root])
    }else {
      ans = Math.max(ans, calc(root))
    }
    
    for(const child of g[root]) {
      help(child)
    }
  }
  function calc(root) {
    let x = 1
    for(let child of g[root]) {
      if(s[root] === s[child]) continue
      let now = new Set()
      dfs(child, root, 1, now)
      x += Math.max(...now)
    }
    memo[root] = x
    return x
  }
  function dfs(c, last, len, t) {
    if(s[c] === s[last] || !g[c]) {
      t.add(len)
      return
    }
    for(const next of g[c]) {
      dfs(next, c, len+1, t)
    }
  }
};